1. Technical Field of the Invention
The present invention relates to information security technologies, and more particularly to a method for generating a one-way function, a device for generating one-way function values, and an authentication method and a device by use of them.
2. Description of the Prior Art
It is a common practice to enclose a private key for performing authentication in a tamper-resistant enclosure such as a smart card to distribute the key. The following authentication system can be configured which uses a private key enclosed in a tamper-resistant enclosure.
For simplicity of description, a distributor of private keys is referred to as a center, tamper-resistant enclosures to store the private keys as tokens, and recipients of the private keys as users.
The center generates a private key x, encloses it in a token, and distributes the token to users. The token is configured so that processing based on the private key x is executable. For example, the token may be configured as described below.
The center defines a public key cryptosystem. For example, let G be a finite Abelian group difficult with discrete logarithm problems (written in additive form for simplicity of notation. Of course, the following discussion can, simply by changing the notation, be applied to even groups conventionally written in multiplicative form); p, a prime number; Fp, the p-elements field; g:Fp→G, a nontrivial homomorphism from the additive group of field Fp to the finite group G; y:Fp→G, the homomorphism defined by y=gx (x is identified to the endomorphism of the additive group of the field Fp defined by multiplication); and π:G→Fp, a mapping. It is well known that we can take the multiplicative group and elliptic curves on finite fields as such finite groups G The token, which has an input-output means, a random number generation means, means for calculating a mapping πg, and means for executing an algorithm with the finite prime field Fp, generates a random number k for an inputted challenge c and outputs response r=(r0, r1) by calculating the following expression:r0=c−π(g(k))r1=k−r0x  [Expression 1]
On the other hand, a verifier, which has an input-output means, a random number generation means, means for calculating homomorphism g, means for calculating homomorphism y, means for executing an algorithm with the finite group G, and means for executing an algorithm with the finite prime field Fp, generates and outputs the challenge c as a random number, and verifies that the following expression is satisfied for the inputted response r:c=r0+π(g(r1)+y(r0)  [Expression 2]
By combining the verifier and the token, authentication can be performed as follows. For the challenge c sent by the verifier, the token sends back, as the response r, a Nyberg-Rueppel signature by the private key x for the challenge c.
This technique is applicable to access control in a way that incorporates a verifier facility in an application program subject to access control, distributes a token as the rights to use the application program, and performs the above-described authentication in the challenge-and-response fashion as required during program execution. Authentication codes in the application program must be protected against analysis to prevent attackers from deleting them.
In direct application of the above-described technique, e.g., when plural independent application programs access-controlled by the same technique are used, although the number of necessary authentication types increases and as many tokens as the number of authentication types are required, the plural authentication types can be supported by only one token as described below.
In this example, the center encloses a private key x different for each token and distributes it to users. Each application program is allocated an authentication identifier aid. When an application program provider grants the rights to use an application program corresponding to an authentication identifier aid to the users, the provider issues a certificate C signed by the provider to the users wherein the certificate includes the authentication identifier aid and a public key y of a user-possessed token.
The application program, during execution of the program, at the timing of authenticating the user's rights, reads the certificate C and verifies the signature, confirms that the described authentication identifier aid is equal to the authentication identifier of the application program, and performs authentication based on the described public key y of the token as described previously.
The method of using a certificate including a public key corresponding to a private key stored in a token as the capability of access rights authentication is excellent in that, provided that the center to distribute private keys enclosed in tokens is a credible third party, plural application program providers having no interests among them can use the method in common and users have only to hold a single token. For example, if a system is configured which in advance incorporates token modules in the CPU, the center will be saved the trouble of distributing the tokens to the users and the users will also be able to use the system without being aware of the tokens.
On the other hand, such a method is undesirable from the viewpoint of users' privacy because public keys of tokens are used as the global identifiers of users, and when capabilities are collected in a large scale, capabilities can be sorted by users.
On the other hand, the following authentication system can be configured which solves the above- described problems by enclosing a private hash function in a tamper-resistant enclosure and distributing it.
In this case, the center generates a private hash function X, encloses it in a token, and distributes the token to a user. The private hash function X is different for each token.
When an application program provider grants a capability representing rights to a user in the form of the certificate C as described previously, for example, the provider includes a token public key y=g(X(aid)) corresponding to a hash value X(aid) generated by a private hash function X for an authentication identifier aid in the certificate C.
This time, since a corresponding public key y is different for each authentication identifier aid, even if capabilities are collected, they cannot be sorted by users.
To authenticate rights for use, a step is only added which inputs an authentication identifier aid for authentication to a token and generates a private key x=X(aid) corresponding to it; other processing is the same.
As an example that a different token has a different private hash function X, in an access rights authenticating device described in Japanese Published Unexamined Patent Application No. H10-247905, capabilities different than in the above description are proposed.
Herein, a pair of a public key y and a private key x to satisfy y=g(x) is defined to depend on only an authentication identifier aid independently of a private hash value X(aid) within a token possessed by each user (e.g., the authentication identifier aid may be a public key y itself), and a capability issued to the user is defined as t=x−X(aid). An amount thus calculated from the private key x and the private hash value X(aid) within a token, i.e., a capability, will be referred to as an access ticket.
The verifier holds a public key y corresponding to an identifier aid of its own and performs the above-described authentication in the challenge-and- response fashion.
The user inputs aid to a token, generates a private hash value X(aid) within the token, and obtains a response r=(r0, r1) using the private key x for a challenge c.
The user further updates the token-outputted response r with an access ticket t using an expression:r1←r1+r0t  [Expression 3]and then sends the response r back to the verifier.
It can be easily confirmed that the updated response r is a Nyberg-Rueppel signature by the private key x for the challenge c.
The access-ticket-based authentication method saves application programs from reading capabilities and verifying the authenticity of capabilities, further simplifying the construction of the verifier (access control codes of the application programs) and providing increased efficiency.
The access-ticket-based authentication method has noticeable characteristics that since processing based on private keys can be performed without disclosing the private keys themselves, which are independent of private hash values generated within tokens, in addition to authentication in the challenge-and-response fashion, processing based on the private keys (e.g., the decryption of cipher text in public key cryptograph and the creation of signature to messages) can be safely committed.
The above-described access control methods based on certificates and access tickets are applicable to not only the execution control of application programs but also, e.g., the control of access to files and the control of access to http servers.
By distributing tokens in the form of portable smart cards or the like and storing capabilities in the tokens, ordinary tickets and cards can be imitated with the digital information of the capabilities.
A variety of authentication methods can be used by enclosing not a private key but a private hash function in a token, as described above.
[Problems of Prior Art]
Hash functions are usually used as fixed functions released as primitives constituting a cryptographic protocol and there are many cases where only standard hash functions such as SHA-1 (Secure Hash Algorithm) and MD5 (Message Digest) are provided in IC chips for encryption. Therefore, in view of the cost of mounting tokens, it is necessary to examine a method for implementing a different private hash function for a different token by using the standard hash functions.
One simple method is to have tokens hold a standard hash function H and a private unique value u different for each token and implement a private hash function X as X(M)=H(u|M).
In this case, although the center may generate u as a random number for each token and hold a tupple (tid, u) of a token identifier and the token private unique value u in a database, if the number of tokens increases, the amount of data would become tremendous and the entries in the database must be kept secret to maintain the above-described authentication system, making the management difficult.
For example, where capabilities of certificate type are used, when a private hash function X of one token leaks, unless the issuer of the capabilities notices the leak, from this point on, each time a certificate C corresponding to the token and the authentication identifier aid is issued, persons knowing the certificate C and a private key x corresponding to it can pass verification without using the token. However, in this case, the leaker can be traced from the private hash value X(M).
Where capabilities of access ticket type are used, when a private hash function X of one token leaks, unless the issuer of the capabilities notices the leak, from this point on, each time an access ticket t corresponding to the token and the authentication identifier aid is issued, a private key x corresponding to the authentication identifier aid as x=t+X(M) is systematically revealed, posing a serious problem. Moreover, in this case, the leaker cannot be traced from the revealed private key x itself.
To reduce the amount of data to be secretly held by the center, a center private unique value s is introduced so that no private unique value is provided for each token. Herein, the private hash function X is implemented as X(M)=H(s|tid|M).
In such a configuration, if the center safely manages only the unique private information s, although it is unnecessary to hold private unique information for each token, global private information swill be enclosed in tokens. Should the assumption of tamper resistance be broken in one token, provided that the token identifier tid is accessible data, there is a danger that private hash functions of all tokens would be revealed in unison.
The authentication method having been heretofore described can be implemented on not only Nyberg-Rueppel signatures on the finite group G difficult with discrete logarithm problems cited as an example but also various public key cryptosystems.
The authentication method is applicable equally to public key cryptosystems based on the difficulty of discrete logarithm problems, such as Diffie-Hellman key sharing, DSA (Digital Signature Algorithm) signature, and Schnorr authentication.
The authentication method is also applicable to public key cryptosystems such as RSA and Guillou-Quisquater authentication based on the difficulty of annihilator decision problems.
In this case, assume that λ is a minimum nonzero integer to annihilate all elements γ (λγ=0) of the finite Abelian group G and it is difficult to decide λ for the finite group G. It is well known that such finite groups G include a multiplicative group (Z/nZ)* of a residue class ring of a rational integer ring Z modulo n where n is an RSA modulus.
For example, Guillou-Quisquater signatures on the finite group G may be adopted as a public key cryptosystem to use, as a capability, a certificate C to prove a public key y=pX(aid) with a private hash value X(aid) as a private key, and an access ticket t=x−X(aid) corresponding to a private key x and a public key y=px may be used as a capability.
RSA on the finite group G is selected as a public key cryptosystem to use an access ticket t=x−X(aid) corresponding to a public key y and a private key x=y−1 as a capability.
In these examples, the private hash value X(aid) is regarded as an element of a finite algebraic system to which private values of a public key cryptosystem belong. The algebraic system to which the private values belong is the finite prime field Fp in the example of discrete logarithm problem systems such as Nyberg-Rueppel signatures, and is the finite group G itself and its faithful action ring z/λZ, respectively, in the example of annihilator decision problem systems such as Guillou-Quisquater signatures and RSA.
In the example of discrete logarithm problem systems, presently, a recommended private key size (about 160 bits) is almost equal to the size of values of hash functions usually used, whereas in the example of annihilator decision problem systems, a recommended private key size (about 1024 bits) is greater than the size of values of hash functions usually used.